#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>
#include <iostream>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define THREAD_COUNT (16)
using namespace std;
const int N = 3e6 + 5;
const int M = 2e5 + 5;
const char numchar[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};


int G1[M][55];
int G2[M][55];
bool can[M];
bool has[M];
string num_string[M];

void prtime(string pos, timeval &time) {
    printf("%s=", pos.c_str());
    struct timeval now;
    gettimeofday(&now, NULL);
    printf("%dms\n", int((now.tv_sec * 1000 + now.tv_usec / 1000) - (time.tv_sec * 1000 + time.tv_usec / 1000)));
    time = now;
}

struct tag_mmap {
    unsigned long long m_size;
    // 要读取源文件的起始内存位置
    void *r_mem;
    // 要写入目标文件的起始内存位置
    void *w_mem;
    // 要复制的大小

} mm[THREAD_COUNT];

struct find_huan {
    int is[M], f[M], num, cur[15], rt;
    bool flag[M];
//    char path[5][70000000];
    string path[5];

    void init() {
        memset(is, -1, sizeof(is));
        memset(f, -1, sizeof(f));
    }

    inline void add_ans(int now_len) {
        string &ss = path[now_len - 3];
        for (int i = 1; i <= now_len; i++) {
            ss += num_string[cur[i]];
        }
        ss[ss.length() - 1] = '\n';
    }


    void dfs(int u, int step) {
        if (u < rt || flag[u]) return;
        if (step > 4 && is[u] != rt) return;
        cur[step] = u;
        if (step >= 3 && f[u] == rt) {
//            len[++num] = step;
            ++num;
            add_ans(step);
        }
        if (step >= 7) return;
        flag[u] = true;
        int stp = step + 1;
        int len = G1[u][0];
//        int idx = upper_bound(G1[u] + 1, G1[u] + len + 1, rt) - G1[u];
        for (int i = 1; i <= len; i++) {
            dfs(G1[u][i], stp);
        }
        flag[u] = false;
    }

    void dfs_ni(int u, int step) {
        flag[u] = true;
//        int len = G2[u][0];
//        for (int i = 1; i <= len; i++) {
//            int v = G2[u][i];
//            if (v < rt || flag[v]) continue;
//            is[v] = rt;
//            if (step == 1) f[v] = rt;
//            if (step == 3) continue;
//            dfs_ni(v, step + 1);
//        }
        int *p = G2[u];
        int len = G2[u][0];
        p++;
        int s = 1;
        while (s <= len) {
            int v = *p;
            ++s;
            ++p;
            if (v < rt || flag[v]) continue;
            is[v] = rt;
            if (step == 1) f[v] = rt;
            if (step == 3) continue;

            dfs_ni(v, step + 1);
        }
        flag[u] = false;
    }

    void start(int l, int r) {
        if (l > r) return;
        for (int i = l; i <= r; i++) {
            if (!has[i])continue;
            if (!can[i]) continue;
            rt = i;
            dfs_ni(i, 1);
            dfs(i, 1);
        }
    }
} T[THREAD_COUNT];


void threadfunc(tag_mmap arg) {
//    timeval s;
//    gettimeofday(&s, NULL);
    char *r = (char *) arg.r_mem;
    char *w = (char *) arg.w_mem;
    memcpy(w, r, arg.m_size);
    munmap(r, arg.m_size);
//    prtime("线程映射答案时间=", s);
}



void find_thread(int s, int t, int k) {
//    timeval time;
//    gettimeofday(&time, NULL);
    T[k].init();
    T[k].start(s, t);
//    prtime("找环线程[" + to_string(k) + "]结束 " + "s = " + to_string(s) + " t=" + to_string(t) + "  ", time);
}

inline string numtostring(int x) {
    string tmp = ",";
    if (x == 0) {
        return "0,";
    }
    while (x != 0) {
        tmp += numchar[x % 10];
        x /= 10;
    }
    reverse(tmp.begin(), tmp.end());
    return tmp;
}
inline string numtostring1(int x) {
    string tmp = "";
    if (x == 0) {
        return "0";
    }
    while (x != 0) {
        tmp += numchar[x % 10];
        x /= 10;
    }
    if(tmp.length() ==1)return tmp;
    reverse(tmp.begin(), tmp.end());
    return tmp;
}


int main() {
//    timeval start;
//    gettimeofday(&start, NULL);
//    timeval time;
//    gettimeofday(&time, NULL);
    char *inputfile = "/data/test_data.txt";
    char *outputfile = "/projects/student/output.txt";
//    char *inputfile = "./data/1004812/test_data.txt";
//    char *inputfile = "./data/2.in";
//    char *outputfile = "./z1.out";

    int m, n = 0;
    //mmap读文件开始
    char *data = NULL;
    int fd = open(inputfile, O_RDONLY);
    long size = lseek(fd, 0, SEEK_END);
    data = (char *) mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    int u, v, cost;
    int tmp = 0;
    int ii = 0, jj = 0;
    int nodenum = 0;
    while (data[ii] != '\0') {
        if (data[ii] >= '0' && data[ii] <= '9') {
            tmp *= 10;
            tmp += data[ii] - '0';
        } else if (data[ii] == ',') {
            if (jj == 0) {
                u = tmp;
                jj++;
            } else if (jj == 1) {
                v = tmp;
                if (!has[u]) {
                    ++nodenum;
                    num_string[u] = numtostring(u);
                    has[u] = 1;
                    n = max(n, u);
                }
                if (!has[v]) {
                    ++nodenum;
                    num_string[v] = numtostring(v) ;
                    has[v] = 1;
                    n = max(n, v);
                }
                int len = ++G1[u][0];
                G1[u][len] = v;
                len = ++G2[v][0];
                G2[v][len] = u;
                if (u < v) can[u] = true;
            }
            tmp = 0;
        } else {
            //cost = tmp;
            //printf("%d\n", w);
            jj = 0;
            tmp = 0;
        }
        ++ii;
    }
    for (int i = 0; i <= n; i++) {
        sort(G1[i] + 1, G1[i] + G1[i][0] + 1);
    }
//    prtime("读数据加建图", time);

    //负载均衡2
    int avg = nodenum / 16;
    tmp = 0;
    int fid = 0;
    int count[20] = {nodenum / 72, nodenum / 72,
                     nodenum / 72, nodenum / 36, nodenum / 36, nodenum / 36, nodenum / 36,nodenum / 24,
                     nodenum / 24,nodenum / 24,nodenum / 8,nodenum / 8,
                     nodenum / 8, nodenum / 8, nodenum / 8};
    int countid = 0;
    std::thread threads[THREAD_COUNT];
    int s = 0;
    for (int i = 0; i <= n; i++) {
        if (has[i]) {
            tmp++;
            if (countid <= 14) {
                if (tmp == count[countid]) {
                    threads[fid] = std::thread(find_thread, s, i, fid);
                    countid++;
                    fid++;
                    s = i + 1;
                    tmp = 0;
                }
            } else {
                threads[fid] = std::thread(find_thread, s, n, fid);
                break;
            }
        }
    }
    for (int i = 0; i < THREAD_COUNT; ++i)
        threads[i].join();

//    prtime("多线程找环结束", time);
    int num = 0;
    for (int i = 0; i < THREAD_COUNT; ++i)num += T[i].num;
    string ans;
//    ans += numtostring(num);
    ans += numtostring1(num);
    ans += '\n';
    ans.reserve(180000000);
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < THREAD_COUNT; ++j)
            ans += T[j].path[i];
    }
//    prtime("多线程拼接答案时间", time);
    //多线程mmap输出
    int wfd;
    wfd = open(outputfile, O_RDWR | O_CREAT | O_TRUNC, 0666);
    lseek(wfd, ans.length() - 1, SEEK_SET);
    write(wfd, "\0", 1);
    const long long nCount = ans.length() / THREAD_COUNT;
    const long long nPages = nCount - (nCount % 4096);
    const long long nSplit = ans.length() - THREAD_COUNT * nPages;
    if (nCount < 4096) {
        void *w_mem = mmap(NULL, ans.length(), PROT_WRITE, MAP_SHARED, wfd, 0);
        memcpy(w_mem, ans.c_str(), ans.length());
        munmap(w_mem, ans.length());
    } else {
//            tag_mmap *mm = new tag_mmap[THREAD_COUNT];
        std::thread threads[THREAD_COUNT];
        for (int i = 0; i < THREAD_COUNT; ++i) {
            if (i < THREAD_COUNT - 1) {
                mm[i].r_mem = (void *) (ans.c_str() + i * nPages);
                mm[i].w_mem = mmap(NULL, nPages, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                mm[i].m_size = nPages;
                threads[i] = std::thread(threadfunc, mm[i]);
            } else {
                mm[i].r_mem = (void *) (ans.c_str() + i * nPages);
                mm[i].w_mem = mmap(NULL, nPages + nSplit, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                mm[i].m_size = nPages + nSplit;
                threads[i] = std::thread(threadfunc, mm[i]);
            }
        }
        for (int join = 0; join < THREAD_COUNT; join++) {
            threads[join].join();
        }
    }
//    prtime("多线程输出时间", time);
//
//    prtime("总时间 ", start);
    return 0;
}